package offer;

import java.util.Arrays;

@FunctionalInterface
public interface NumWays {
    int numWays(int steps, int arrLen);
}

/**
 * 暴力破解实现，超时
 */
class NumWaysImpl1 implements NumWays{

    static final int MOD_NUM =(int) (1e10 + 7);
    @Override
    public int numWays(int steps, int arrLen) {
        if(steps > 10){return 0;}
        return search(0, 0, steps, arrLen);
    }
    private int search(int curIndex, int curStep, int steps, int arrLen){
        if(curIndex >= 0 && curIndex < arrLen){
            if(curStep == steps){
                if(curIndex == 0){
                    return 1;
                }else {
                    return 0;
                }
            }else{
                int stay = search(curIndex, curStep + 1, steps, arrLen);
                int goLeft = search(curIndex - 1, curStep + 1, steps, arrLen);
                int goRight = search(curIndex + 1, curStep + 1, steps, arrLen);
                return (stay + goLeft + goRight) % MOD_NUM;
            }
        }else {
            return 0;
        }
    }
}
class NumWaysTest {
    static final int[] TEST_01 = new int[]{4,2};
    public static void main(String[] args) {
        new NumWaysImpl2().numWays(TEST_01[0], TEST_01[1]);
    }
}

class NumWaysImpl2 implements NumWays{
    static final int MODULO =(int) (1e9 + 7);
    public int numWays(int steps, int arrLen) {

        int maxColumn = Math.min(arrLen - 1, steps);
        int[][] dp = new int[steps + 1][maxColumn + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - 1 >= 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MODULO;
                }
                if (j + 1 <= maxColumn) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MODULO;
                }
            }
        }
        return dp[steps][0];
    }
}
